package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 树的几种遍历方式 {

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        TreeNode h = new TreeNode(8);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        e.left = h;

        List<Integer> nodes = new ArrayList<>();
        preOrder1(nodes, a);
        System.out.println(nodes);
        nodes.clear();

        preOrder2(nodes, a);
        System.out.println(nodes);
        nodes.clear();

        List<List<Integer>> levelOrder = new ArrayList<>();
        levelOrder1(levelOrder, a, 0);
        System.out.println(levelOrder);

    }


    /**
     * 1 前序遍历 根节点在前面 (根 左 右) 递归法
     */
    public static void preOrder1(List<Integer> nodes, TreeNode node) {
        if (node == null) {
            return;
        }
        nodes.add(node.val);
        preOrder1(nodes, node.left);
        preOrder1(nodes, node.right);
    }

    /**
     * 2 前序遍历 根节点在前面 (根 左 右) 循环法
     */
    public static void preOrder2(List<Integer> nodes, TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(node);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            nodes.add(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }


    /**
     * 中序遍历 根节点在中间 (左 根 右)
     */
    public static List<Integer> inOrder(TreeNode head) {
        List<Integer> nodes = new ArrayList<>();
        inOrder1(nodes, head);
        return nodes;
    }

    // 1 中序遍历 递归
    public static void inOrder1(List<Integer> nodes, TreeNode node) {
        if (node == null) {
            return;
        }
        preOrder1(nodes, node.left);
        nodes.add(node.val);
        preOrder1(nodes, node.right);
    }

    // 2 中序遍历 使用栈
    public static void inOrder2(List<Integer> result, TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            result.add(pop.val);
            root = pop.right;
        }
    }


    /**
     * 后序遍历 根节点在后面 (左 右 根)
     */
    public static List<Integer> postOrder(TreeNode head) {
        List<Integer> nodes = new ArrayList<>();
        postOrder1(nodes, head);
        return nodes;
    }

    // 1 递归后序遍历
    public static void postOrder1(List<Integer> nodes, TreeNode node) {
        if (node == null) {
            return;
        }
        preOrder1(nodes, node.left);
        preOrder1(nodes, node.right);
        nodes.add(node.val);
    }


    // 递归层级遍历
    public static void levelOrder1(List<List<Integer>> nodes, TreeNode node, int level) {
        if (node == null) {
            return;
        }
        List<Integer> list;
        if (level >= nodes.size()) {
            list = new ArrayList<>();
            nodes.add(level, list);
        } else {
            list = nodes.get(level);
        }
        list.add(node.val);
        if (node.left != null) {
            levelOrder1(nodes, node.left, level + 1);
        }
        if (node.right != null) {
            levelOrder1(nodes, node.right, level + 1);
        }
    }

}
